//Given an array nums containing n distinct numbers in the range [0, n], return 
//the only number in the range that is missing from the array. 
//
// 
// Example 1: 
//
// 
//Input: nums = [3,0,1]
//Output: 2
//Explanation: n = 3 since there are 3 numbers, so all numbers are in the range 
//[0,3]. 2 is the missing number in the range since it does not appear in nums.
// 
//
// Example 2: 
//
// 
//Input: nums = [0,1]
//Output: 2
//Explanation: n = 2 since there are 2 numbers, so all numbers are in the range 
//[0,2]. 2 is the missing number in the range since it does not appear in nums.
// 
//
// Example 3: 
//
// 
//Input: nums = [9,6,4,2,3,5,7,0,1]
//Output: 8
//Explanation: n = 9 since there are 9 numbers, so all numbers are in the range 
//[0,9]. 8 is the missing number in the range since it does not appear in nums.
// 
//
// Example 4: 
//
// 
//Input: nums = [0]
//Output: 1
//Explanation: n = 1 since there is 1 number, so all numbers are in the range [0
//,1]. 1 is the missing number in the range since it does not appear in nums.
// 
//
// 
// Constraints: 
//
// 
// n == nums.length 
// 1 <= n <= 104 
// 0 <= nums[i] <= n 
// All the numbers of nums are unique. 
// 
//
// 
// Follow up: Could you implement a solution using only O(1) extra space complex
//ity and O(n) runtime complexity? 
// Related Topics 位运算 数组 哈希表 数学 排序 
// 👍 449 👎 0


package leetcode.editor.cn;

//Java：Missing Number
class P268MissingNumber {
    public static void main(String[] args) {
        Solution solution = new P268MissingNumber().new Solution();
        // TO TEST
        solution.missingNumber(new int[]{1});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int missingNumber(int[] nums) {
            int max = Integer.MIN_VALUE;
            int sum = 0;
            int min = Integer.MAX_VALUE;
            for (int num : nums) {
                sum += num;
                max = Integer.max(max, num);
                min = Integer.min(min, num);
            }
            int len = max;
            int ori = len * (len + 1) / 2;

            return ori - sum == 0 ? (min == 0 ? max + 1 : 0) : ori - sum;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}